﻿#include <iostream>
#include <utility>  // for std::pair
#include <cassert>
#include <stack>
using namespace std;
//
//// 定义 AVL 树节点结构
//struct Node {
//    // 键值对，first 为键，second 为值
//    pair<int, int> kv;
//    // 平衡因子：右子树高度 - 左子树高度
//    int bf;
//    // 父节点、左子节点、右子节点指针
//    Node* parent;
//    Node* left;
//    Node* right;
//
//    // 构造函数
//    Node(pair<int, int> p)
//        : kv(p), bf(0), parent(nullptr), left(nullptr), right(nullptr) {
//    }
//};
//
//class AVLTree {
//private:
//    Node* root;  // 根节点
//
//    // 辅助函数：获取节点高度（简化版，实际应维护高度或通过遍历计算）
//    int getHeight(Node* node) {
//        if (node == nullptr) return 0;
//        // 这里为了演示，直接返回基于平衡因子的推导（实际需真实维护高度）
//        // 真实场景应单独维护 height 字段或递归计算
//        return 1 + max(getHeight(node->left), getHeight(node->right));
//    }
//
//    // 旋转操作声明（实际需实现左旋、右旋等，这里仅示意）
//    void rotateLeft(Node*& node) { /* ... */ }
//    void rotateRight(Node*& node) { /* ... */ }
//
//public:
//    AVLTree() : root(nullptr) {}
//
//    // 插入函数（对外接口）
//    bool insert(pair<int, int> kv) {
//        return insert(root, kv);
//    }
//
//private:
//    // 插入函数（递归/迭代实现，这里用迭代方式演示）
//    bool insert(Node*& root, pair<int, int> kv) {
//        // 1. 普通 BST 插入逻辑
//        Node* cur = nullptr;
//        Node* parent = nullptr;
//        Node* newNode = new Node(kv);
//
//        // 找到插入位置
//        cur = root;
//        while (cur != nullptr) {
//            parent = cur;
//            if (kv.first < cur->kv.first) {
//                cur = cur->left;
//            }
//            else if (kv.first > cur->kv.first) {
//                cur = cur->right;
//            }
//            else {
//                // 键已存在，插入失败（根据需求决定是否覆盖值）
//                delete newNode;
//                return false;
//            }
//        }
//
//        // 2. 插入新节点
//        cur = newNode;
//        if (parent == nullptr) {
//            // 树为空，新节点作为根
//            root = cur;
//        }
//        else {
//            if (kv.first < parent->kv.first) {
//                parent->left = cur;
//            }
//            else {
//                parent->right = cur;
//            }
//            // 维护父指针
//            cur->parent = parent;
//        }
//
//        // 3. 更新平衡因子并检测旋转
//        while (parent != nullptr) {
//            // 更新平衡因子
//            if (cur == parent->left) {
//                // 左子树高度变化，平衡因子减 1
//                parent->bf--;
//            }
//            else {
//                // 右子树高度变化，平衡因子加 1
//                parent->bf++;
//            }
//
//            // 根据平衡因子判断后续操作
//            if (parent->bf == 0) {
//                // 平衡因子为 0，子树高度未变化，无需继续更新
//                break;
//            }
//            else if (parent->bf == 1 || parent->bf == -1) {
//                // 平衡因子为 ±1，子树高度变化但仍平衡，继续向上更新
//                cur = parent;
//                parent = parent->parent;
//            }
//            else if (parent->bf == 2 || parent->bf == -2) {
//                // 平衡因子为 ±2，子树不平衡，需要旋转处理
//                if (parent->bf == 2) {
//                    // 右子树过高，需左旋或右旋-左旋（根据情况）
//                    if (cur->bf == 1) {
//                        // 右-右情况，左旋
//                        rotateLeft(parent);
//                    }
//                    else {
//                        // 右-左情况，右旋再左旋
//                        rotateRight(cur);
//                        rotateLeft(parent);
//                    }
//                }
//                else {
//                    // 左子树过高，需右旋或左旋-右旋（根据情况）
//                    if (cur->bf == -1) {
//                        // 左-左情况，右旋
//                        rotateRight(parent);
//                    }
//                    else {
//                        // 左-右情况，左旋再右旋
//                        rotateLeft(cur);
//                        rotateRight(parent);
//                    }
//                }
//                // 旋转后，整棵树恢复平衡，无需继续向上更新
//                break;
//            }
//            else {
//                // 平衡因子异常，断言报错
//                assert(false);
//            }
//        }
//
//        return true;
//    }
//};
//
//
//
//
//
//
//
//
////
////// 示例：左旋函数（需根据实际类结构调整）
////template <typename K, typename V>
////void AVLTree<K, V>::rotateLeft(Node<K, V>*& node) {
////    Node<K, V>* rightChild = node->right;
////    node->right = rightChild->left;
////    if (rightChild->left != nullptr) {
////        rightChild->left->parent = node;
////    }
////    rightChild->parent = node->parent;
////    if (node->parent == nullptr) {
////        _root = rightChild;
////    }
////    else if (node == node->parent->left) {
////        node->parent->left = rightChild;
////    }
////    else {
////        node->parent->right = rightChild;
////    }
////    rightChild->left = node;
////    node->parent = rightChild;
////
////    // 更新平衡因子（需根据实际高度调整，示例简化处理）
////    node->bf = 0;
////    rightChild->bf = 0;
////}
//
//
//// 假设 Node 结构体和 AVL 树类的基础定义（需提前声明）
//template <typename K, typename V>
//struct Node {
//    pair<K, V> kv;       // 键值对：first 是键，second 是值
//    int bf;              // 平衡因子：右子树高度 - 左子树高度
//    Node* parent;        // 父节点指针
//    Node* left;          // 左子节点指针
//    Node* right;         // 右子节点指针
//
//    // 构造函数：用键值对初始化节点
//    Node(const pair<K, V>& p)
//        : kv(p), bf(0), parent(nullptr), left(nullptr), right(nullptr) {
//    }
//};
//
//template <typename K, typename V>
//class AVLTree {
//private:
//    Node<K, V>* _root;   // 根节点指针
//
//public:
//    AVLTree() : _root(nullptr) {}  // 构造函数：初始化空树
//
//    // 对外接口：插入键值对
//    bool Insert(const pair<K, V>& kv) {
//        // 1. 树为空时，直接创建根节点
//        if (_root == nullptr) {
//            _root = new Node<K, V>(kv);
//            return true;
//        }
//
//        Node<K, V>* parent = nullptr;  // 记录当前节点的父节点
//        Node<K, V>* cur = _root;       // 从根节点开始查找插入位置
//
//        // 2. 查找插入位置（类似 BST 插入逻辑）
//        while (cur != nullptr) {
//            if (cur->kv.first < kv.first) {
//                // 键更大，去右子树找
//                parent = cur;
//                cur = cur->right;
//            }
//            else if (cur->kv.first > kv.first) {
//                // 键更小，去左子树找
//                parent = cur;
//                cur = cur->left;
//            }
//            else {
//                // 键已存在，插入失败（根据需求可选择覆盖值）
//                return false;
//            }
//        }
//
//        // 3. 创建新节点并链接到父节点
//        cur = new Node<K, V>(kv);     // 为新键值对创建节点
//        if (parent->kv.first < kv.first) {
//            parent->right = cur;      // 新节点作为父节点的右孩子
//        }
//        else {
//            parent->left = cur;       // 新节点作为父节点的左孩子
//        }
//        cur->parent = parent;         // 维护父指针
//
//        // 4. 更新平衡因子（从新节点的父节点开始向上更新）
//        while (parent != nullptr) {
//            // 判断当前节点是父节点的左还是右子树，更新父节点平衡因子
//            if (cur == parent->left) {
//                parent->bf--;         // 左子树高度增加，平衡因子减 1
//            }
//            else {
//                parent->bf++;         // 右子树高度增加，平衡因子加 1
//            }
//
//            // 根据平衡因子的值决定后续操作
//            if (parent->bf == 0) {
//                // 平衡因子为 0，说明父节点子树高度未变化，停止更新
//                break;
//            }
//            else if (parent->bf == 1 || parent->bf == -1) {
//                // 平衡因子为 ±1，子树仍平衡但高度变化，继续向上更新
//                cur = parent;         // 向上回溯到父节点
//                parent = parent->parent; // 继续处理更上层父节点
//            }
//            else if (parent->bf == 2 || parent->bf == -2) {
//                // 平衡因子为 ±2，子树不平衡，需要旋转处理（此处需补充旋转逻辑）
//                // ********** 旋转修复逻辑需在此补充 **********
//                break;
//            }
//            else {
//                // 平衡因子异常（如 ±3），断言报错
//                assert(false);
//            }
//        }
//
//        return true;  // 插入成功
//    }
//};
using namespace std; 
//﻿   int main()
//{
//
//    stack<char> S;
//
//    char x, y;
//
//    x = 'n'; y = 'g';
//
//    S.push(x); S.push('i'); S.push(y);
//
//    S.pop(); S.push('r'); S.push('t'); S.push(x);
//
//    S.pop(); S.push('s');
//
//    while (!S.empty())
//
//    {
//
//        x = S.top();
//
//        S.pop();
//
//        cout << x;
//
//    };
//
//    cout << y;
//    return 0;
//}
//
﻿void main()
//
//{
//
//    queue<char> Q;
//
//    char x, y;
//
//    x = 'n'; y = 'g';
//
//    Q.push(x); Q.push('i'); Q.push(y);
//
//    Q.pop(); Q.push('r'); Q.push('t'); Q.push(x);
//
//    Q.pop(); Q.push('s');
//
//    while (!Q.empty())
//
//    {
//
//        x = Q.front();
//
//        Q.pop();
//
//        cout << x;
//
//    };
//
//    cout << y;
//
//}

//queue.push(root);
//while (!queue.empty())
//{
//    node = queue.top();
//    queue.pop();
//    output(node->value)    //输出节点对应数字
//
//        if (node->left)
//            queue.push(node->left);
//    if (node->right)
//        queue.push(node->right);
//}

﻿int main()

{

    priority_queue<int> a;

    priority_queue<int, vector<int>, greater<int> > c;

    priority_queue<string> b;

    for (int i = 0; i < 5; i++)

    {

        a.push(i);

        c.push(i);

    }

    while (!a.empty())

    {

        cout << a.top() << ' ';

        a.pop();

    }

    cout << endl;

    while (!c.empty())

    {

        cout << c.top() << ' ';

        c.pop();

    }

    cout << endl;

    b.push("abc");

    b.push("abcd");

    b.push("cbd");

    while (!b.empty())

    {

        cout << b.top() << ' ';

        b.pop();

    }

    cout << endl;

    return 0;

}

